package com.company.堆栈队列;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * @param
 * @author jianjian.zhang
 * @date 2022/07/23 17:01
 * @return
 * @description: 思路：将中缀表达式转换为后缀表达式
 * 步骤：   (左括号"("默认优先级是最低的， 右括号")"默认优先级是最高的)
 * 1.初始化两个栈，运算符栈s1和数字栈s2;
 * 2.从左向右扫描中缀表达式；
 * 3.遇到数字时，入数字栈s2;
 * 4.遇到运算符时，比较其与s1栈顶元素的优先级；
 * 4.1. 如果s1为空，或者栈顶运算符为"(",则直接将次运算符加入到s1栈；
 * 4.2. 否则，若优先级比栈顶元素的优先级高，则直接加入到s1栈中；
 * 4.3. 否则，将s1栈顶的运算符弹出加入到s2中；
 * 5. 遇到括号时：
 * 5.1. 如果是左括号"(",直接加入到s1栈中
 * 5.2. 如果是右括号")"，则以次弹出s1栈顶的运算符，并加入到s2中，直到遇到左括号为止，此时将这一对括号丢弃
 * 6. 重复步骤2到步骤5，直到遍历完中缀表达式
 * 7， 将s1中剩余的运算符弹出加入到s2中。
 */

public class 带括号的计算器的实现 {

    public static void main(String[] args) {
        short s1= 1;
        s1 = (short) (s1 + 1);
        int i = s1 + 1;
        Scanner scanner = new Scanner(System.in);
        String expression = scanner.nextLine();
        List<String> centerList = AnalyticExpression(expression);
        List<String> postfixList = toPostfixExpression(centerList);
        int res = calculator(postfixList);
        System.out.println(postfixList);
        System.out.println(res);
    }

    /**
     * 中缀表达式转成集合
     *
     * @param expression
     * @return
     */
    public static List<String> AnalyticExpression(String expression) {

        List<String> list = new ArrayList<>();
        char c;
        String str = "";  //用于拼接多位数
        int i = 0;
        while (i < expression.length()) {
            if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) {
                list.add(c + "");
                i++;
            } else {
                str = "";
                while (i < expression.length() && ((c = expression.charAt(i)) >= 48 && (c = expression.charAt(i)) <= 57)) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }

    /**
     * 中缀表达式转成后缀表达式
     *
     * @param centerList
     * @return
     */
    private static List<String> toPostfixExpression(List<String> centerList) {
        List<String> list = new ArrayList<>();
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        for (int i = 0; i < centerList.size(); i++) {
            if (centerList.get(i).matches("\\d+")) {
                s2.push(centerList.get(i));
            } else if ("*".equals(centerList.get(i)) || "/".equals(centerList.get(i)) || "+".equals(centerList.get(i)) || "-".equals(centerList.get(i))) {
                if (s1.isEmpty() || "(".equals(s1.peek())) {
                    s1.push(centerList.get(i));
                } else if (getLevel(centerList.get(i)) > getLevel(s1.peek())) {
                    s1.push(centerList.get(i));
                } else {
                    s2.push(s1.pop());
                    s1.push(centerList.get(i));
                }
            } else {
                if ("(".equals(centerList.get(i))) {
                    s1.push(centerList.get(i));
                } else if (")".equals(centerList.get(i))) {
                    while (!"(".equals(s1.peek())) {
                        s2.push(s1.pop());
                    }
                    s1.pop();  //  弹出左括号"("
                }
            }
        }
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
        while (!s1.isEmpty()) {
            list.add(s1.pop());
        }
        return list;

    }

    private static int getLevel(String str) {
        int level = 0;
        if ("*".equals(str) || "/".equals(str)) {
            level = 1;
        }
        return level;
    }


    /**
     * 计算值后缀表达式
     *
     * @param list
     * @return
     */
    private static int calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;
                switch (s) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num1 - num2;
                        break;
                    case "*":
                        result = num1 * num2;
                        break;
                    case "/":
                        result = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("运算符不在 + - * / 内");
                }
                stack.push(String.valueOf(result));
            }
        }
        return Integer.parseInt(stack.peek());
    }
}
